package dfs;

/**
 * Created by fengliejv on 2021/12/19.
 */
public class BattleshipsInABoard419 {
    int result = 0;

    int[][] direct = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public int countBattleships(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return result;
        }
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[0].length; j++) {
                visited[i][j] = false;
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(visited, board, i, j,true);
            }
        }
        return result;
    }

    private void dfs(boolean[][] visited, char[][] board, int x, int y, boolean b) {
        if(x<0 || x>= visited.length || y <0 || y>=visited[0].length){
            return;
        }
        if (visited[x][y]) {
            return;
        }
        visited[x][y] = true;

        if(board[x][y] == 'X'){
            if(b){
                result++;
            }
            for (int i = 0; i < direct.length; i++) {
                dfs(visited,board,x+direct[i][0],y+direct[i][1],false);
            }
        }
    }
}
